package distinctDifferenceArray;

public class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        // 不同元素的数目
        int n = nums.length;
        int[] pre = new int[n];
        pre[0] = 1;
        int[] marks1 = new int[51];
        marks1[nums[0]] = 1;
        for (int i = 1; i < n; i++) {
            if(marks1[nums[i]] == 0) {
                marks1[nums[i]] = 1;
                pre[i] = pre[i-1] + 1;
            }else {
                pre[i] = pre[i-1];
            }
        }
        int[] bac = new int[n];
        int[] mask2 = new int[51];
        for (int i = n-2; i >=0 ; i--) {
            if(mask2[nums[i+1]] == 0) {
                mask2[nums[i+1]] = 1;
                bac[i] = bac[i+1] + 1;
            }else {
                bac[i] = bac[i+1];
            }
        }
        int[] dif = new int[n];
        for (int i = 0; i < nums.length; i++) {
            dif[i] = pre[i] - bac[i];
        }
        return dif;
    }
}
